/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */
var makesquare = function(matchsticks) {
  // 初始化状态判断
  if(matchsticks == null || matchsticks.length < 4) {
    return false;
  }
  let sum = 0;
  for(let i = 0; i < matchsticks.length; i++) {
    sum += matchsticks[i];
  }
  if(sum % 4 != 0) return false;
  let borderLength = sum / 4; // 边长
  matchsticks = matchsticks.sort((a, b) => (b - a));
  if(matchsticks[matchsticks.length - 1] > borderLength) return false;
  let result = new Array(4).fill(0);

  function dfs(depth) {
    if(depth == matchsticks.length) {
      return (result[0] != 0) && (result[0] == result[1] && result[1] == result[2] && result[2] == result[3]);
    }
    for(let i = 0; i < 4; i++) {
      if(result[i] + matchsticks[depth] <= borderLength) {
        result[i] += matchsticks[depth];
        if(dfs(depth + 1)) {
          return true;
        }
        result[i] -= matchsticks[depth];
      }
    }
    return false;
  }
  return dfs(0);
};
let matchsticks = [1,1,2,2,2];
console.log(makesquare(matchsticks));
matchsticks = [3,3,3,3,4];
console.log(makesquare(matchsticks));
matchsticks = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,6];
console.log(makesquare(matchsticks));
matchsticks = [9,38,1,76,41,19,3,97,48,5,83,15,51,99,95];
console.log(makesquare(matchsticks));
matchsticks = [14,10,10,10,10,10,10,10,10,10,10,10,8,9,19];
console.log(makesquare(matchsticks));
